10272. Reduce to one

 

Consider a list of integers L. Initially L contains the integers 1 through n, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in L is not important. You should perform the following operation n – 1 times:

·        Choose two elements of the list, let’s denote them by x and y. These two elements may be equal.

·        Erase the chosen elements from L.

·        Append the number x + y + x * y to L.

At the end, L contains exactly one integer. Find the maximum possible value of this integer. Since the answer may be large, compute it modulo 109 + 7.

 

Input. The first line contains the number of test cases t. Each of the next t lines contains a single integer n (1 ≤ n ≤ 106).

 

Output. For each test case, print a single line containing one integer – the maximum possible value of the final number in the list modulo 109 + 7.

 

Sample input

Sample ouutput

3

1

2

4

1

5

119

 

 

SOLUTION

mathematics

 

Algorithm analysis

Transform the expression:

x + y + x * y = y * (x + 1) + (x + 1) – 1 = (x + 1) * (y + 1) – 1

After removing the numbers x and y from the list, the number (x + 1) * (y + 1) – 1 will be inserted.

If you further remove (x + 1) * (y + 1) – 1 and z from the list, the next number will be inserted:

((x + 1) * (y + 1) – 1 + 1) * (z + 1) – 1 =

(x + 1) * (y + 1) * (z + 1) – 1

By analogy, it can be stated that if initially

L = {a1, a2, …, an},

then at the end there will be a number (a1 + 1) * (a2 + 1) * … * (an + 1) – 1.

Since initially L contains integers from 1 to n, at the end there will be a number

(1 + 1) * (2 + 1) * … * (n + 1) – 1 = (n + 1)! – 1

 

Algorithm realization

Declare the constants.

 

#define MOD 1000000007

#define MAX 1000002

 

The input contains several test cases. Declare an array p such that p[i] = i!.

 

long long p[MAX];

 

Read the number of test cases tests. Compute the factorials of numbers, and store p[i] = i!

 

scanf("%d", &tests);

p[1] = 1;

for (i = 2; i < MAX; i++)

  p[i] = (p[i - 1] * i) % MOD;

 

Process the test cases. For each input value of n print (n + 1)! – 1.

 

while (tests--)

{

  scanf("%d", &n);

  printf("%lld\n", p[n + 1] - 1);

}

 

Python realization

Declare the constants.

 

MOD = 1000000007

MAX = 1000002

 

Compute the factorials of numbers, and store p[i] = i!

 

p = [1] * MAX

for i in range(2, MAX):

  p[i] = (p[i - 1] * i) % MOD

 

Read the number of test cases tests.

 

tests = int(input())

 

Process the test cases. For each input value of n print (n + 1)! – 1.

 

for _ in range(tests):

  n = int(input())

  print(p[n + 1] - 1)